/*
题目: 旋转数字
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

https://leetcode.cn/problems/rotated-digits
 */
public class RotatedDigits {
    final int[] diffs = new int[] {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
    char[] cs = null;
    int[][] memo = null;
    int size = 0;

    public int rotatedDigits(int n) {
        cs = String.valueOf(n).toCharArray();
        size = cs.length;
        // 数位 DP 中的 memo 数组一维容量取决于题目, 到第 i 位的状态需求
        // 该题中需要出现 2,5,6,9 至少一次, 所以到第 i 位只需要两个状态即可
        memo = new int[size][2];

        for (int i = 0; i < size; i ++)
            Arrays.fill(memo[i], -1);

        // 这个题前导 0 对结果没有影响, [1, n] 的每个数都对前导 0 没有要求
        return dfs(0, 0, true);
    }

    private int dfs(int pos, int hasDiff, boolean limited) {
        // 完成一个路径, 并且至少有一个 2,5,6,9
        if (pos >= size)    return hasDiff;

        if (!limited && memo[pos][hasDiff] != -1)   return memo[pos][hasDiff];

        int src = 0;
        for (int i = 0, up = limited ? cs[pos] - '0' : 9; i <= up; i ++) {
            if (diffs[i] != -1) {
                src += dfs(pos + 1, hasDiff | diffs[i], limited && i == up);
            }
        }

        if (!limited) {
            memo[pos][hasDiff] = src;
        }
        return src;
    }
}
